package com.algorithms.sorts;

/**
 * MergeSort<br>
 * Complexity O(N*logN)<br><br>
 * 
 * bases on the idea of merging 2 sorted arrays into 1 (complexity: O(N))
 * <br><br>
 * we first divide the array into 2 smaller arrays, try to sort 2 arrays 
 * individually. then we merge them using above merging solution.
 * <br>
 * to sort 1 array, we apply recursive loop on above step, until we meet
 * a smallest array which contains only 1 item.
 * 
 * @author minhld
 *
 */
public class MergeSort extends Sort{
	
	public MergeSort(int[] dataArray, int dataLength){
		super(dataArray, dataLength);
		this.sortName = "MergeSort";
	}
	
	@Override
	public int[] sort(){
		int[] copyData = new int[this.length];
		mergeSort(copyData, 0, this.length - 1);
		this.data = copyData;
		return this.data;
	}
	
	private void mergeSort(int[] arr, int firstIdx, int secondIdx){
		if (firstIdx == secondIdx){
			// 1 item
			this.numOfProcess++;
			return;
		}else {
			int midIdx = (int)Math.floor((firstIdx + secondIdx) / 2);
			mergeSort(arr, firstIdx, midIdx);
			mergeSort(arr, midIdx + 1, secondIdx);
			merge(arr, firstIdx, midIdx, secondIdx);
		}
	}
	
	private void merge(int[] arr, int firstIdx, int midIdx, int secondIdx){
		int leftIdx = firstIdx, rightIdx = midIdx + 1, combineIdx = firstIdx;
		
		// compare items between two arrays to fill into the combine array
		while (leftIdx <= midIdx && rightIdx <= secondIdx){
			if (this.data[leftIdx] < this.data[rightIdx]){
				arr[combineIdx++] = this.data[leftIdx++];
			}else{
				arr[combineIdx++] = this.data[rightIdx++];
			}

			// minor step
			this.numOfProcess++;
			this.numOfCopy++;
		}
		
		// copy the rest of left array if any
		while (leftIdx <= midIdx){
			arr[combineIdx++] = this.data[leftIdx++];
			this.numOfCopy++;
		}
		
		// copy the rest of right array if any
		while (rightIdx <= secondIdx){
			arr[combineIdx++] = this.data[rightIdx++];
			this.numOfCopy++;
		}
	
		// copy back to data
		for (int i = firstIdx; i <= secondIdx; i++){
			this.data[i] = arr[i];
			this.numOfCopy++;
		}
	}
}
